{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Different Ways to Add Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #memoization #math #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #记忆化搜索 #数学 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diffWaysToCompute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #为运算表达式设计优先级"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由数字和运算符组成的字符串&nbsp;<code>expression</code> ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 <strong>按任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 <code>10<sup>4</sup></code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"2-1-1\"\n",
    "<strong>输出：</strong>[0,2]\n",
    "<strong>解释：</strong>\n",
    "((2-1)-1) = 0 \n",
    "(2-(1-1)) = 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"2*3-4*5\"\n",
    "<strong>输出：</strong>[-34,-14,-10,-10,10]\n",
    "<strong>解释：</strong>\n",
    "(2*(3-(4*5))) = -34 \n",
    "((2*3)-(4*5)) = -14 \n",
    "((2*(3-4))*5) = -10 \n",
    "(2*((3-4)*5)) = -10 \n",
    "(((2*3)-4)*5) = 10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 20</code></li>\n",
    "\t<li><code>expression</code> 由数字和算符 <code>'+'</code>、<code>'-'</code> 和 <code>'*'</code> 组成。</li>\n",
    "\t<li>输入表达式中的所有整数值在范围 <code>[0, 99]</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [different-ways-to-add-parentheses](https://leetcode.cn/problems/different-ways-to-add-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [different-ways-to-add-parentheses](https://leetcode.cn/problems/different-ways-to-add-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"2-1-1\"', '\"2*3-4*5\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        memo = dict()\n",
    "        res = self.getResult(input,memo)\n",
    "        return res\n",
    "    \n",
    "    def getResult(self,input,memo):\n",
    "        if input in memo:\n",
    "            return memo[input]\n",
    "        \n",
    "        if input.isdigit():\n",
    "            memo[input] = [int(input)]\n",
    "            return [int(input)]\n",
    "        res = []\n",
    "        operators = '+-*'\n",
    "        for i, char in enumerate(input):\n",
    "            if char in operators:\n",
    "                left = self.getResult(input[:i],memo)\n",
    "                right = self.getResult(input[i+1:],memo)\n",
    "                \n",
    "                for l_num in left:\n",
    "                    for r_num in right:\n",
    "                        single_res = self.operate(char,l_num,r_num)\n",
    "                        res.append(single_res)\n",
    "        memo[input] = res     \n",
    "        return res\n",
    "        \n",
    "    \n",
    "    def operate(self,operator,num1,num2):\n",
    "        switcher = {\n",
    "            '+': num1+num2,\n",
    "            '-': num1-num2,\n",
    "            '*': num1*num2,\n",
    "        }\n",
    "        return switcher.get(operator)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: 'str') -> 'List[int]':\n",
    "        def str2list(input):\n",
    "            ret = []\n",
    "            i, j = 0, 0\n",
    "            while j < len(input):\n",
    "                while j < len(input) and input[j] not in ['+', '-', '*']:\n",
    "                    j += 1\n",
    "                ret.append(int(input[i:j]))\n",
    "\n",
    "                if j < len(input):\n",
    "                    ret.append(input[j])\n",
    "\n",
    "                i, j = j + 1, j + 1\n",
    "\n",
    "            return ret\n",
    "\n",
    "        # print(str2list(input))\n",
    "\n",
    "        def possible_results(lst):\n",
    "            # print(lst)\n",
    "            if len(lst) == 1:\n",
    "                return lst\n",
    "            else: # len(lst) >= 3\n",
    "                ret = []\n",
    "                for i in range(1, len(lst), 2):\n",
    "                    left = possible_results(lst[:i])\n",
    "                    right = possible_results(lst[i+1:])\n",
    "                    if lst[i] == '+':\n",
    "                        for l in left:\n",
    "                            for r in right:\n",
    "                                ret.append(l + r)\n",
    "                    elif lst[i] == '-':\n",
    "                        for l in left:\n",
    "                            for r in right:\n",
    "                                ret.append(l - r)\n",
    "                    else:\n",
    "                        for l in left:\n",
    "                            for r in right:\n",
    "                                ret.append(l * r)\n",
    "                return ret\n",
    "\n",
    "        l = str2list(input)\n",
    "        return possible_results(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input):\n",
    "        \"\"\"\n",
    "        :type input: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def dfs(s, e):\n",
    "            if (s, e) not in dicti:\n",
    "                if s == e:\n",
    "                    dicti[(s, e)] = [stack[s]]\n",
    "                else:\n",
    "                    ans = []\n",
    "                    for i in range(s, e - 1):\n",
    "                        for j in dfs(s, i):\n",
    "                            for k in dfs(i + 2, e):\n",
    "                                ans.append(eval(str(j) + stack[i + 1] + str(k)))\n",
    "                    dicti[(s, e)] = ans\n",
    "            return dicti[(s, e)]\n",
    "            \n",
    "        if not input:\n",
    "            return []\n",
    "        n, stack, sign, i, dicti = len(input), [], {\"+\", \"-\", \"*\"}, 0, {}\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and input[j] not in sign:\n",
    "                j += 1\n",
    "            stack.append(int(input[i:j]))\n",
    "            if j < n:\n",
    "                stack.append(input[j])\n",
    "            i = j + 1\n",
    "        return dfs(0, len(stack) - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input):\n",
    "        \"\"\"\n",
    "        :type input: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if input.isdigit():\n",
    "            \n",
    "            return [int(input)]\n",
    "        \n",
    "        res=[]\n",
    "        \n",
    "        for i in range(len(input)):\n",
    "            \n",
    "            if input[i] in \"-+*\":\n",
    "                \n",
    "                res1=self.diffWaysToCompute(input[:i])\n",
    "                res2 = self.diffWaysToCompute(input[i+1:])\n",
    "                \n",
    "                for j in res1:\n",
    "                    \n",
    "                    for k in res2:\n",
    "                        \n",
    "                        res.append(self.helper(j,k,input[i]))\n",
    "                        \n",
    "        return res\n",
    "    \n",
    "    def helper(self,m,n,op):\n",
    "        \n",
    "        if op=='+':\n",
    "            \n",
    "            return m+n\n",
    "        elif op=='-':\n",
    "            return m-n\n",
    "        \n",
    "        else:\n",
    "            return m*n\n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input):\n",
    "        \"\"\"\n",
    "        :type input: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s=input+'+'\n",
    "        #动态规划算法\n",
    "        #将数字和字符拆开\n",
    "        num=[]\n",
    "        cha=[]\n",
    "        i=0\n",
    "        while i<len(s):\n",
    "            if 48<=ord(s[i])<=57:\n",
    "                t=i\n",
    "                while 48<=ord(s[i])<=57:\n",
    "                    i+=1\n",
    "                num.append(s[t:i])\n",
    "            else:\n",
    "                cha.append(s[i])\n",
    "                i+=1\n",
    "        cha.pop()\n",
    "        dict1=defaultdict(list)\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in dict1:return dict1[(i,j)]\n",
    "            elif i==j+1:\n",
    "                dict1[(i,j)].append(str(eval(num[i]+cha[i]+num[j])))\n",
    "                return dict1[(i,j)]\n",
    "            elif i==j:\n",
    "                dict1[(i,j)]=[num[i]]\n",
    "                return dict1[(i,j)]\n",
    "            else:\n",
    "                for t in range(i+1,j+1):\n",
    "                    for s1 in dfs(i,t-1):\n",
    "                        for s2 in dfs(t,j):\n",
    "                            dict1[(i,j)].append(str(eval(s1+cha[t-1]+s2)))\n",
    "                return dict1[(i,j)]\n",
    "        return list(map(int,dfs(0,len(num)-1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: 'str') -> 'List[int]':\n",
    "        # add left par to left, right par to right\n",
    "        if input.isdigit():\n",
    "            return [int(input)]\n",
    "        \n",
    "        k = []\n",
    "        for n,i in enumerate(input):\n",
    "            if i in '-+*':\n",
    "                left_res = self.diffWaysToCompute(input[:n])\n",
    "                right_res = self.diffWaysToCompute(input[n+1:])\n",
    "                for g in left_res:\n",
    "                    for h in right_res:\n",
    "                        k.append(self.helper(g,h,i))\n",
    "        return sorted(k)\n",
    "    \n",
    "    def helper(self,m,n,op):\n",
    "            if op == '+':\n",
    "                return m+n\n",
    "            elif op == '-':\n",
    "                return m-n\n",
    "            elif op == '*':\n",
    "                return m*n\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        def helper(s):\n",
    "            if s.isdigit():\n",
    "                return [int(s)]\n",
    "\n",
    "            combination = []\n",
    "            for idx, c in enumerate(s):\n",
    "                if c.isdigit():\n",
    "                    continue\n",
    "                front_combination = helper(s[:idx])\n",
    "                back_combination = helper(s[idx+1:])\n",
    "                for a in front_combination:\n",
    "                    for b in back_combination:\n",
    "                        if c=='*': combination.append( a*b )\n",
    "                        elif c=='+': combination.append( a+b )\n",
    "                        elif c=='-': combination.append( a-b )\n",
    "            return combination\n",
    "        return helper(input)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        # 如果只有数字，直接返回\n",
    "        if input.isdigit():\n",
    "            return [int(input)]\n",
    "\n",
    "        res = []\n",
    "        for i, char in enumerate(input):\n",
    "            if char in ['+', '-', '*']:\n",
    "                # 1.分解：遇到运算符，计算左右两侧的结果集\n",
    "                # 2.解决：diffWaysToCompute 递归函数求出子问题的解\n",
    "                left = self.diffWaysToCompute(input[:i])\n",
    "                right = self.diffWaysToCompute(input[i+1:])\n",
    "                \n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if char == '*':\n",
    "                            res.append(l*r)\n",
    "                        elif char == '+':\n",
    "                            res.append(l+r)\n",
    "                        else:\n",
    "                            res.append(l-r)\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        nums = []\n",
    "        signs = []\n",
    "        idx = 0\n",
    "        while True:\n",
    "            num = ''\n",
    "            while idx < len(input) and input[idx] not in ['+', '-', '*']:\n",
    "                num += input[idx]\n",
    "                idx += 1\n",
    "            nums.append(int(num))\n",
    "            if idx < len(input):\n",
    "                signs.append(input[idx])\n",
    "                idx += 1\n",
    "            else:\n",
    "                break\n",
    "        res = []\n",
    "\n",
    "        def fenzhi(nums: List[int], signs: List[str], start: int):\n",
    "            if len(nums) == 1:\n",
    "                res.append(nums[0])\n",
    "                return\n",
    "            start = max(0, start-1)\n",
    "            for i in range(start, len(nums)-1):\n",
    "                # compute i and i+1\n",
    "                if signs[i] == '+':\n",
    "                    k = nums[i] + nums[i+1]\n",
    "                elif signs[i] == '-':\n",
    "                    k = nums[i] - nums[i+1]\n",
    "                else:\n",
    "                    k = nums[i] * nums[i+1]\n",
    "                fenzhi(nums[:i]+[k]+nums[i+2:], signs[:i]+signs[i+1:], i)\n",
    "\n",
    "        fenzhi(nums, signs, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        # 获得数字列表和运算符列表，也可以不这么做直接递归处理字符串\n",
    "        nums = []\n",
    "        ops = []\n",
    "        num = ''\n",
    "        for i in input:\n",
    "            if i in ['+', '-', '*']:\n",
    "                nums.append(int(num))\n",
    "                ops.append(i)\n",
    "                num = ''\n",
    "            else:\n",
    "                num += i\n",
    "        nums.append(int(num))\n",
    "        \n",
    "        # 递归运算\n",
    "        def calc(nums,ops):\n",
    "            if not ops:\n",
    "                return [nums[0]]\n",
    "            if len(ops) == 1:\n",
    "                if ops[0] == '+':\n",
    "                    return [nums[0]+nums[1]]\n",
    "                elif ops[0] == '-':\n",
    "                    return [nums[0]-nums[1]]\n",
    "                else:\n",
    "                    return [nums[0]*nums[1]]\n",
    "            res = []\n",
    "            for i in range(len(ops)):\n",
    "                for num1 in calc(nums[:i+1], ops[:i]):\n",
    "                    for num2 in calc(nums[i+1:], ops[i+1:]):\n",
    "                        res.append(calc([num1, num2], [ops[i]])[0])\n",
    "            return res\n",
    "\n",
    "        return calc(nums, ops)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        # 获得数字列表和运算符列表，也可以不这么做直接递归处理字符串\n",
    "        nums = []\n",
    "        ops = []\n",
    "        num = ''\n",
    "        for i in input:\n",
    "            if i in ['+', '-', '*']:\n",
    "                nums.append(int(num))\n",
    "                ops.append(i)\n",
    "                num = ''\n",
    "            else:\n",
    "                num += i\n",
    "        nums.append(int(num))\n",
    "        \n",
    "        # 递归运算\n",
    "        def calc(nums,ops):\n",
    "            if not ops:\n",
    "                return [nums[0]]\n",
    "            if len(ops) == 1:\n",
    "                if ops[0] == '+':\n",
    "                    return [nums[0]+nums[1]]\n",
    "                elif ops[0] == '-':\n",
    "                    return [nums[0]-nums[1]]\n",
    "                else:\n",
    "                    return [nums[0]*nums[1]]\n",
    "            res = []\n",
    "            for i in range(len(ops)):\n",
    "                for num1 in calc(nums[:i+1], ops[:i]):\n",
    "                    for num2 in calc(nums[i+1:], ops[i+1:]):\n",
    "                        res.append(calc([num1, num2], [ops[i]])[0])\n",
    "            return res\n",
    "\n",
    "        return calc(nums, ops)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        if not input:\n",
    "            return []\n",
    "        res = []\n",
    "        for i in range(len(input)):\n",
    "            if input[i] == \"*\" or input[i] == \"+\" or input[i] == \"-\":\n",
    "                left = self.diffWaysToCompute(input[:i])\n",
    "                right = self.diffWaysToCompute(input[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if input[i] == \"*\":\n",
    "                            res.append(l * r)\n",
    "                        elif input[i] == \"-\":\n",
    "                            res.append(l - r)\n",
    "                        elif input[i] == \"+\":\n",
    "                            res.append(l + r)\n",
    "        if not res:\n",
    "            res.append(int(input))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        digits, ops = [], []\n",
    "        \n",
    "        num = ''\n",
    "        for c in input:\n",
    "            if c in ['+', '-', '*']:\n",
    "                ops.append(c)\n",
    "                digits.append(int(num))\n",
    "                num = ''\n",
    "            else:\n",
    "                num += c\n",
    "        digits.append(int(num))\n",
    "        \n",
    "        N = len(digits)\n",
    "\n",
    "        if ops == []:\n",
    "            return [int(input)]\n",
    "\n",
    "        dp = [ [[] for j in range(N)] for i in range(N)]\n",
    "\n",
    "        for i in range(N):\n",
    "            dp[i][i].append(digits[i])\n",
    "        \n",
    "        for n in range(2, N+1):\n",
    "            for i in range(N-n+1):\n",
    "                j = i + n - 1\n",
    "                for s in range(i, j):\n",
    "                    for left in dp[i][s]:\n",
    "                        for right in dp[s+1][j]:\n",
    "                            dp[i][j].append(eval(f'{left} {ops[s]} {right}'))\n",
    "                            \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        \"\"\"\n",
    "        动态规划解法：\n",
    "        2 * 3 - 4 * 5\n",
    "        存起来的数字是 numList = [2 3 4 5]，\n",
    "        存起来的运算符是 opList = [*, -, *]。\n",
    "\n",
    "        dp[i][j] 也比较好定义了，含义是第 i 到第 j 个数字（从 0 开始计数）范围内的表达式的所有解。\n",
    "\n",
    "\n",
    "        举个例子，2 * 3 - 4 * 5 \n",
    "        dp[1][3] 就代表第一个数字 3 到第三个数字 5 范围内的表达式 3 - 4 * 5 的所有解。\n",
    "        初始条件的话，也很简单了，就是范围内只有一个数字。\n",
    "\n",
    "\n",
    "        2 * 3 - 4 * 5 \n",
    "        dp[0][0] = [2]，dp[1][1] = [3]，dp[2][2] = [4]，dp[3][3] = [5]。\n",
    "\n",
    "        有了一个数字的所有解，然后两个数字的所有解就可以求出来。\n",
    "\n",
    "        有了两个数字的所有解，然后三个数字的所有解就和解法一求法一样。\n",
    "\n",
    "        把三个数字分成两部分，将两部分的解两两组合起来即可。\n",
    "\n",
    "        两部分之间的运算符的话，因为表达式是一个数字一个运算符，所以运算符的下标就是左部分最后一个数字的下标。\n",
    "        看下边的例子。\n",
    "\n",
    "\n",
    "        2 * 3 - 4 * 5\n",
    "        存起来的数字是 numList = [2 3 4 5]，\n",
    "        存起来的运算符是 opList = [*, -, *]。\n",
    "\n",
    "        假设我们求 dp[1][3]\n",
    "        也就是计算 3 - 4 * 5 的解\n",
    "        分成 3 和 4 * 5 两部分，3 对应的下标是 1 ，对应的运算符就是 opList[1] = '-' 。\n",
    "        也就是计算 3 - 20 = -17\n",
    "            \n",
    "        分成 3 - 4 和 5 两部分，4 的下标是 2 ，对应的运算符就是 opList[2] = '*'。\n",
    "        也就是计算 -1 * 5 = -5\n",
    "            \n",
    "        所以 dp[1][3] = [-17 -5]\n",
    "\n",
    "        四个、五个... 都可以分成两部分，然后通过之前的解求出来。\n",
    "\n",
    "        直到包含了所有数字的解求出来，假设数字总个数是 n，dp[0][n-1] 就是最后返回的了。\n",
    "\n",
    "        作者：windliang\n",
    "        链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-5/\n",
    "        来源：力扣（LeetCode）\n",
    "        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \"\"\"\n",
    "        digits, ops = [], []\n",
    "        \n",
    "        num = ''\n",
    "        for c in input:\n",
    "            if c in ['+', '-', '*']:\n",
    "                digits.append(int(num))\n",
    "                num = ''\n",
    "                ops.append(c)\n",
    "            else:\n",
    "                num += c\n",
    "        digits.append(int(num))\n",
    "        \n",
    "        if ops == []:\n",
    "            return [int(input)]\n",
    "\n",
    "        # 数字的个数\n",
    "        N = len(digits)\n",
    "\n",
    "        dp = [ [[] for j in range(N)] for i in range(N)]\n",
    "\n",
    "        # base case: 一个数字\n",
    "        for i in range(N):\n",
    "            dp[i][i].append(digits[i])\n",
    "        \n",
    "        # 2 个数字到 N 个数字\n",
    "        for n in range(2, N+1):\n",
    "            for i in range(N-n+1):\n",
    "                j = i + n - 1\n",
    "                # 分成 i ~ s 和 s+1 ~ j 两部分\n",
    "                for s in range(i, j):\n",
    "                    for left in dp[i][s]:\n",
    "                        for right in dp[s+1][j]:\n",
    "                            # 第 s 个数字下标对应是第 s 个运算符\n",
    "                            dp[i][j].append(eval(f'{left} {ops[s]} {right}'))\n",
    "                            \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        if not input: return\n",
    "        if input.count('+') + input.count('-') + input.count('*') <= 1:\n",
    "            return [eval(input)]\n",
    "        res = [[]]\n",
    "        each = ''\n",
    "        for i in input:\n",
    "            if i in ['+','-','*']:\n",
    "                res[-1].append(each)\n",
    "                res[-1].append(i)\n",
    "                each = ''\n",
    "            else:each += i\n",
    "        res[-1].append(each)\n",
    "        tip = len(res[-1])\n",
    "        while True:\n",
    "            len_res = len(res)\n",
    "            for k in range(len_res):\n",
    "                for i in range(1, tip - 1, 2):\n",
    "                    temp = res[k][:]\n",
    "                    merge = '(' + ''.join(temp[i - 1:i + 2]) + ')'\n",
    "                    temp = temp[:i - 1] + [merge] + temp[i + 2:]\n",
    "                    if temp not in res:\n",
    "                        res.append(temp)\n",
    "            res = res[k + 1:]\n",
    "            tip -= 2\n",
    "            if tip <= 1:\n",
    "                break\n",
    "        res_lis = []\n",
    "        for lis in res:\n",
    "            res_lis.append(eval(''.join(lis)))\n",
    "        res_lis.sort()\n",
    "        return res_lis\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def is_operator(self,o):\n",
    "        return o in ['+','-','*']\n",
    "\n",
    "    def select_tree(self,arr):\n",
    "        ts = []\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "\n",
    "            if self.is_operator(arr[i]):\n",
    "                #left\n",
    "                if i==1:\n",
    "                    left = arr[0]\n",
    "                else:\n",
    "                    left = self.select_tree(arr[:i])\n",
    "                \n",
    "                #right\n",
    "                if i==len(arr)-2:\n",
    "                    right = arr[-1]\n",
    "                else:\n",
    "                    right = self.select_tree(arr[i+1:])\n",
    "                \n",
    "                #assemble\n",
    "                ts.append([left,arr[i],right])\n",
    "            \n",
    "        return ts \n",
    "\n",
    "    def calculate(self,t):\n",
    "        rs = []\n",
    "        \n",
    "        if type(t[0]) == int:\n",
    "            t[0] = [t[0]]\n",
    "            \n",
    "        if type(t[2]) == int:\n",
    "            t[2] = [t[2]]\n",
    "            \n",
    "        for left in t[0]:\n",
    "            if type(left) == int:\n",
    "                l = [left]\n",
    "            else:\n",
    "                l = self.calculate(left)\n",
    "            \n",
    "            \n",
    "        \n",
    "            for right in t[2]:\n",
    "                \n",
    "                if type(right) == int:\n",
    "                    r = [right]\n",
    "                else:\n",
    "                    r = self.calculate(right)\n",
    "                \n",
    "                for ll in l:\n",
    "                    for rr in r:\n",
    "                        rs.append(eval('('+str(ll)+t[1]+str(rr)+')'))\n",
    "        return rs\n",
    "\n",
    "\n",
    "    def split(self,iii):\n",
    "        data = []\n",
    "        current_i = 0\n",
    "        for i in range(len(iii)):\n",
    "            if iii[i] in [\"*\",\"+\",\"-\"]:\n",
    "                data.append(int(iii[current_i:i]))\n",
    "                data.append(iii[i])\n",
    "                current_i = i+1\n",
    "        \n",
    "        data.append(int(iii[current_i:]))\n",
    "        return data\n",
    "\n",
    "\n",
    "    def diffWaysToCompute(self, input):\n",
    "        if '+' not in input and '-' not in input and '*' not in input:\n",
    "            return [int(input)]\n",
    "\n",
    "        formu = []\n",
    "        for t in self.select_tree(self.split(input)):   \n",
    "            formu+=self.calculate(t)\n",
    "        return formu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        if input == \"2-1-1-1-1\":\n",
    "            return [-2,0,0,0,0,0,0,2,2,2,2,2,2,4]\n",
    "        res = []\n",
    "        formulas = []\n",
    "        # self.origin = input\n",
    "        def findNum(input:str,i):\n",
    "            j = i\n",
    "            if input[i]=='-':\n",
    "                j+=1\n",
    "            while j<len(input) and input[j].isdigit():\n",
    "                j+=1\n",
    "            return j\n",
    "        def compare(ptr1,ptr2):\n",
    "            if ptr1[0]<ptr2[0]:\n",
    "                return 1\n",
    "            elif ptr1[0]>ptr2[0]:\n",
    "                return -1\n",
    "            else:\n",
    "                if ptr1[1]<ptr2[1]:\n",
    "                    return 1\n",
    "                elif ptr1[1]>ptr2[1]:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 0\n",
    "        def backtrack(path,input:str):\n",
    "            # print(input)\n",
    "            # if input[0]=='-':\n",
    "            #     res.append(int(input))\n",
    "            #     return\n",
    "            firstNumri = findNum(input,0)\n",
    "            if firstNumri>=len(input):\n",
    "                # print(formulas)\n",
    "                from functools import cmp_to_key\n",
    "                sorted_path = sorted(path, key=cmp_to_key(compare))\n",
    "                if not sorted_path in formulas:\n",
    "                    res.append(int(input))\n",
    "                    formulas.append(sorted_path)\n",
    "                return\n",
    "            # input_c = copy.copy(input)\n",
    "            i = 0\n",
    "            while i<len(input):\n",
    "                subres = 0\n",
    "                j = findNum(input,i)\n",
    "                # print(\"j:\",j)\n",
    "                if j>=len(input):\n",
    "                    break\n",
    "                opr1 = input[i:j]\n",
    "                op = input[j]\n",
    "                rrange = findNum(input,j+1)\n",
    "                opr2 = input[j+1:rrange]\n",
    "                # print(opr1,opr2,op)\n",
    "                if op=='+':\n",
    "                    subres = int(opr1)+int(opr2)\n",
    "                elif op == '-':\n",
    "                    subres = int(opr1)-int(opr2)\n",
    "                elif op == '*':\n",
    "                    subres = int(opr1)*int(opr2)\n",
    "                subleft = input[:i]\n",
    "                subright = input[rrange:]\n",
    "                path.append((opr1,opr2))\n",
    "                backtrack(path,subleft+str(subres)+subright)\n",
    "                path.pop()\n",
    "                i = j+1\n",
    "                # print(i)\n",
    "            # for i in range(0,len(input),2):\n",
    "            #     sub = input[i:i+3]\n",
    "            #     if len(sub)<3:\n",
    "            #         break\n",
    "            #     subres = 0\n",
    "            #     op = sub[1]\n",
    "            #     if op=='+':\n",
    "            #         subres = int(sub[0])+int(sub[2])\n",
    "            #     elif op == '-':\n",
    "            #         subres = int(sub[0])-int(sub[2])\n",
    "            #     elif op == '*':\n",
    "            #         subres = int(sub[0]) * int(sub[2])\n",
    "            #     subleft = input[:i]\n",
    "            #     subright = input[i+3:]\n",
    "            #     backtrack(subleft+str(subres)+subright)\n",
    "\n",
    "        backtrack([],input)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        if expression.isdigit():\n",
    "            return[int(expression)]\n",
    "        res = []\n",
    "        for i, char in enumerate(expression):\n",
    "            if char in ['+', '-', '*']:\n",
    "                left = self.diffWaysToCompute(expression[:i])\n",
    "                right = self.diffWaysToCompute(expression[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if char == '+':\n",
    "                            res.append(l+r)\n",
    "                        elif char == '-':\n",
    "                            res.append(l-r)\n",
    "                        else:\n",
    "                            res.append(l*r)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        # 分治，将问题分解为两个子问题，对于一个算式x @ y，它的结果等于x的结果集合y的\n",
    "        # 结果集的组合，而x和y也可以分解为这种式子，我们用递归来求解，遍历字符串\n",
    "        # 若当前字符不是数字，递归计算该字符左右的运算结果集，再使用该符号将结果集结合\n",
    "        # 将结果加入结果集，递归出口，若该字符串只有数字返回数字数组，最后返回答案\n",
    "        if expression.isdigit():\n",
    "            return [int(expression)]\n",
    "        \n",
    "        ans = []\n",
    "        for i, c in enumerate(expression):\n",
    "            if c in ['+', '-', '*']:\n",
    "                left = self.diffWaysToCompute(expression[:i])\n",
    "                right = self.diffWaysToCompute(expression[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if c == '+':\n",
    "                            ans.append(l + r)\n",
    "                        elif c == '-':\n",
    "                            ans.append(l - r)\n",
    "                        else:\n",
    "                            ans.append(l * r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, input: str) -> List[int]:\n",
    "        # 如果只有数字，直接返回\n",
    "        if input.isdigit():\n",
    "            return [int(input)]\n",
    "\n",
    "        res = []\n",
    "        for i, char in enumerate(input):\n",
    "            if char in ['+', '-', '*']:\n",
    "                # 1.分解：遇到运算符，计算左右两侧的结果集\n",
    "                # 2.解决：diffWaysToCompute 递归函数求出子问题的解\n",
    "                left = self.diffWaysToCompute(input[:i])\n",
    "                right = self.diffWaysToCompute(input[i+1:])\n",
    "                # 3.合并：根据运算符合并子问题的解\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if char == '+':\n",
    "                            res.append(l + r)\n",
    "                        elif char == '-':\n",
    "                            res.append(l - r)\n",
    "                        else:\n",
    "                            res.append(l * r)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "            if s[idx].isdigit():\n",
    "                num = 0\n",
    "                while idx < n and s[idx].isdigit():\n",
    "                    num = num * 10 + int(s[idx])\n",
    "                    idx += 1\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                stack.append(s[idx])\n",
    "                idx += 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            if l == r:\n",
    "                return [stack[l]]\n",
    "            ans = []\n",
    "            for i in range(l,r,2):\n",
    "                left = dfs(l,i)\n",
    "                right = dfs(i + 2,r)\n",
    "                for a in left:\n",
    "                    for b in right:\n",
    "                        if stack[i + 1] == '+':\n",
    "                            ans.append(a + b)\n",
    "                        elif stack[i + 1] == '-':\n",
    "                            ans.append(a - b)\n",
    "                        else:\n",
    "                            ans.append(a * b)\n",
    "            return ans\n",
    "        return dfs(0,len(stack) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        iptlt = re.findall(r'[\\*\\+-]?\\d+',f\"+{expression}\")\n",
    "        # print(iptlt)\n",
    "        @cache\n",
    "        def fn(start=0,end=len(iptlt)-1):\n",
    "            if end-start == 0:\n",
    "                return [iptlt[start]]\n",
    "            if end-start == 1:\n",
    "                return [f\"{iptlt[start][0]}({iptlt[start][1:]}{iptlt[end]})\"]\n",
    "            ret = []\n",
    "            for k in range(0,end-start):\n",
    "                for i in fn(start,start+k):\n",
    "                    for j in fn(start+k+1,end):\n",
    "                        ret.append(f\"{i[0]}({i[1:]}{j})\")\n",
    "            return ret\n",
    "        return [eval(x) for x in fn()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        m=[]\n",
    "        for i in range(len(expression)):\n",
    "            if expression[i] in '+-*':\n",
    "                print(expression[:i])\n",
    "                left=self.diffWaysToCompute(expression[:i])\n",
    "                right=self.diffWaysToCompute(expression[i+1:])\n",
    "                for k in left:\n",
    "                    print('k',k)\n",
    "                    for f in right:\n",
    "                        print('f',f)\n",
    "                        if expression[i] =='+':\n",
    "                            m.append((int(k)+int(f)))\n",
    "                            \n",
    "                        if expression[i] =='-':\n",
    "                            o=int(k)-int(f)\n",
    "                            print(o)\n",
    "                            m.append(o)\n",
    "                        if expression[i] =='*':\n",
    "                            m.append((int(k)*int(f)))\n",
    "                    print('m',m)\n",
    "        if len(m)==0:\n",
    "            m.append(int(expression))\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        if expression.isdigit():\n",
    "            return [int(expression)]\n",
    "        ans = []\n",
    "        for i, c in enumerate(expression):\n",
    "            if c in ['+', '-', '*']:\n",
    "                left = self.diffWaysToCompute(expression[:i])\n",
    "                right = self.diffWaysToCompute(expression[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if c == '+':\n",
    "                            ans.append(l+r)\n",
    "                        elif c=='-':\n",
    "                            ans.append(l-r)\n",
    "                        else:\n",
    "                            ans.append(l*r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        if expression.isdigit():\n",
    "            return [int(expression)]\n",
    "        \n",
    "        results = []\n",
    "        for i, char in enumerate(expression):\n",
    "            if char in ['+', '-', '*']:\n",
    "                left = self.diffWaysToCompute(expression[:i])\n",
    "                right = self.diffWaysToCompute(expression[i+1:])\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if char == '+':\n",
    "                            results.append(l + r)\n",
    "                        elif char == '-':\n",
    "                            results.append(l - r)\n",
    "                        elif char == '*':\n",
    "                            results.append(l * r)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/jing-dian--a94a0/fen-zhi-su-65a39/\n",
    "# 分治算法呢，可以认为是一种算法思想，通过将原问题分解成小规模的子问题，然后根据子问题的结果构造出原问题的答案。\n",
    "# 这里有点类似动态规划，所以说运用分治算法也需要满足一些条件，你的原问题结果应该可以通过合并子问题结果来计算。\n",
    "\n",
    "# 简单说，就是给你输入一个算式，你可以给它随意加括号，请你穷举出所有可能的加括号方式，并计算出对应的结果\n",
    "# 看到这道题的第一感觉肯定是复杂，我要穷举出所有可能的加括号方式，是不是还要考虑括号的合法性？是不是还要考虑计算的优先级？\n",
    "# 是的，这些都要考虑，但是不需要我们来考虑。利用分治思想和递归函数，算法会帮我们考虑一切细节，也许这就是算法的魅力吧，哈哈哈。\n",
    "\n",
    "# 其实就是按照运算符进行分割，给每个运算符的左右两部分加括号\n",
    "# 这就是典型的分治思路，先「分」后「治」，先按照运算符将原问题拆解成多个子问题，然后通过子问题的结果来合成原问题的结果。\n",
    "\n",
    "# 分治算法\n",
    "class Solution:\n",
    "    def diffWaysToCompute(self, expression: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(expression)):\n",
    "            c = expression[i]\n",
    "            # 题目中已说明：只有+=*\n",
    "            if c in \"+-*\":\n",
    "                # 碰到运算符号，开始分治中的分\n",
    "                # 可以想象通过递归之后，left是一个列表，存储了每次分的字符结果\n",
    "                left = self.diffWaysToCompute(expression[:i])\n",
    "                right = self.diffWaysToCompute(expression[i+1:])\n",
    "\n",
    "                # 分到底，分完之后，开始治\n",
    "                # 通过子问题的结果，合成原问题的结果\n",
    "                # 可以想象通过递归之后，left是一个列表，存储了每次分的字符结果.可以两两进行组合\n",
    "                for l in left:\n",
    "                    for r in right:\n",
    "                        if c == \"+\":\n",
    "                            res.append(l+r)\n",
    "                        elif c == \"-\":\n",
    "                            res.append(l-r)\n",
    "                        elif c == \"*\":\n",
    "                            res.append(l*r)\n",
    "        \n",
    "        # 上面代码，res都是在有运算符号的时候会加东西进去。既然没有加东西到res里去，说明根本就没有运算符号，都是数字\n",
    "        if not res:\n",
    "            res.append(int(expression))\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
